//全排列
// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

class Solution {
private:
    vector<int> path;
    vector<vector<int>> results;
    void dfs(vector<bool>& visited, vector<int>& nums){
        int n = nums.size();
        if(path.size()==n){
            results.push_back(path);
            return;
        }

        for(int i=0; i<n; i++){
            if(visited[i] == false){
                visited[i] = true;
                path.push_back(nums[i]);
                dfs(visited, nums);
                visited[i] = false;
                path.pop_back();
            }
        }
        return;
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<bool> visited(n,false);
        dfs(visited,nums);
        return results;
    }
};